//A binary tree is named Even-Odd if it meets the following conditions: 
//
// 
// The root of the binary tree is at level index 0, its children are at level in
//dex 1, their children are at level index 2, etc. 
// For every even-indexed level, all nodes at the level have odd integer values 
//in strictly increasing order (from left to right). 
// For every odd-indexed level, all nodes at the level have even integer values 
//in strictly decreasing order (from left to right). 
// 
//
// Given the root of a binary tree, return true if the binary tree is Even-Odd, 
//otherwise return false. 
//
// 
// Example 1: 
//
// 
//
// 
//Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
//Output: true
//Explanation: The node values on each level are:
//Level 0: [1]
//Level 1: [10,4]
//Level 2: [3,7,9]
//Level 3: [12,8,6,2]
//Since levels 0 and 2 are all odd and increasing, and levels 1 and 3 are all ev
//en and decreasing, the tree is Even-Odd.
// 
//
// Example 2: 
//
// 
//
// 
//Input: root = [5,4,2,3,3,7]
//Output: false
//Explanation: The node values on each level are:
//Level 0: [5]
//Level 1: [4,2]
//Level 2: [3,3,7]
//Node values in the level 2 must be in strictly increasing order, so the tree i
//s not Even-Odd.
// 
//
// Example 3: 
//
// 
//
// 
//Input: root = [5,9,1,3,5,7]
//Output: false
//Explanation: Node values in the level 1 should be even integers.
// 
//
// Example 4: 
//
// 
//Input: root = [1]
//Output: true
// 
//
// Example 5: 
//
// 
//Input: root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
//Output: true
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the tree is in the range [1, 105]. 
// 1 <= Node.val <= 106 
// 
// Related Topics 树 广度优先搜索 二叉树 
// 👍 16 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

//Java：Even Odd Tree
class P1609EvenOddTree {
    public static void main(String[] args) {
        Solution solution = new P1609EvenOddTree().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        //BFS
        public boolean isEvenOddTreeBFS(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int depth = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                TreeNode pre = null;
                while (size-- > 0) {
                    TreeNode poll = queue.poll();
                    if (poll.left != null) {
                        queue.offer(poll.left);
                    }
                    if (poll.right != null) {
                        queue.offer(poll.right);
                    }
                    if (depth % 2 == 0 && poll.val % 2 == 1) {
                        if (pre == null || poll.val > pre.val) {
                            pre = poll;
                            continue;
                        }
                        return false;
                    } else if (depth % 2 == 1 && poll.val % 2 == 0) {
                        if (pre == null || poll.val < pre.val) {
                            pre = poll;
                            continue;
                        }
                        return false;
                    } else {
                        return false;
                    }
                }
                depth++;

            }
            return true;
        }

        public boolean isEvenOddTree(TreeNode root) {
            return isEvenOddTree(root, 0, new ArrayList<>());
        }

        private boolean isEvenOddTree(TreeNode root, int depth, ArrayList<Integer> mList) {
            if (root == null) {
                return true;
            }
            if (depth % 2 == root.val % 2) {
                return false;
            }
            if (mList.size() > depth) {
                //根据当前节点是奇数层还是偶数层，来判断是递增还是递减
                if ((depth % 2 == 0) && mList.get(depth) >= root.val) {
                    return false;
                } else if (depth % 2 == 1 && mList.get(depth) <= root.val) {
                    return false;
                } else {
                    mList.set(depth, root.val);
                }
            } else {
                mList.add(root.val);
            }
            return isEvenOddTree(root.left, depth + 1, mList) && isEvenOddTree(root.right, depth + 1, mList);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}